package 力扣;

/**
 * @Classname _142环形链表_II
 * @Description TODO
 * @Date 2020/12/14 21:27
 * @Created by xiaok
 */
public class _142环形链表_II {

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    /*思路
     * 1.先找环,记录相遇的位置，相遇的位置一定是起点到起始环节点的距离。
     * 2.然后定义一个从起点出发, 另一个从相遇位置出发，相遇时正好为起始环节点。
     * */
    public ListNode detectCycle(ListNode head) {
        // 步骤一：使用快慢指针判断链表是否有环
        ListNode p = head, p2 = head;
        boolean hasCycle = false;
        while (p2 != null && p2.next != null) {
            p = p.next;
            p2 = p2.next.next;
            if (p == p2) {
                hasCycle = true;
                break;
            }
        }

        // 步骤二：若有环，找到入环开始的节点
        if (hasCycle) {
            ListNode q = head;
            while (p != q) {
                p = p.next;
                q = q.next;
            }
            return q;
        } else
            return null;
    }

}
